package two.chapter_2.c2_4;

import two.chapter_2.c2_1.Sortable;

/**
 * 堆排序：
 * 步骤：  1，构造一个有序堆，最大元素在第一位
 *        2，交换第一个元素和最后一个元素，此时最大元素出现在最后一位
 *        3，元素总数减1
 *        4，第一个元素做下沉操作，找到剩余元素中的最大值，重新使堆有序
 * @param <Item>
 */
public class HeapSort<Item extends Comparable<Item>> extends Sortable<Item> {


    @Override
    public void sort(Item[] items) {
        int N=items.length;
        //构造一个有序堆
        for (int k=N/2;k>=1;k--){
            sink(items,k,N);
        }
        //
        while (N>1){
            exch(items,1,N--);
            sink(items,1,N);
        }
    }

    /***************************************************************************
     * Helper functions to restore the heap invariant.
     ***************************************************************************/
    private static void sink(Comparable[] pq, int k, int n) {
        while (2*k <= n) {
            int j = 2*k;
            if (j < n && less(pq, j, j+1)) j++;
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }

    /***************************************************************************
     * Helper functions for comparisons and swaps.
     * Indices are "off-by-one" to support 1-based indexing.
     ***************************************************************************/
    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i-1].compareTo(pq[j-1]) < 0;
    }

    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i-1];
        pq[i-1] = pq[j-1];
        pq[j-1] = swap;
    }

}
